Iterative refinement is a long-standing technique for improving the accuracy of a computed solution to a nonsingular linear system $Ax = b$ obtained via LU factorization. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix $A$ has condition number safely less than the reciprocal of the unit roundoff, $u$. We identify a mechanism that allows iterative refinement to produce solutions with normwise relative error of order $u$ to systems with condition numbers of order $u^{-1}$ or larger, provided that the update equation is solved with a relative error sufficiently less than $1$. A new rounding error analysis is given and its implications are analyzed. Building on the analysis, we develop a GMRES-based iterative refinement method (GMRES-IR) that makes use of the computed LU factors as preconditioners. GMRES-IR exploits the fact that even if $A$ is extremely ill conditioned the LU factors contain enough information that preconditioning can greatly reduce the condition number of $A$. Our rounding error analysis and numerical experiments show that GMRES-IR can succeed where standard refinement fails, and that it can provide accurate solutions to systems with condition numbers of order $u^{-1}$ and greater. Indeed in our experiments with such matrices---both random and from the University of Florida Sparse Matrix Collection---GMRES-IR yields a normwise relative error of order $u$ in at most $3$ steps in every case.
展开▼
机译:迭代细化是提高通过LU分解获得的非奇异线性系统$ Ax = b $的计算解的准确性的一项长期技术。它利用以超高精度计算的残差,通常是工作精度的两倍,并且如果矩阵$ A $的条件数安全地小于单位四舍五入的倒数$ u $,则现有结果可保证收敛。我们确定了一种机制,该机制可以迭代地生成条件序号为$ u ^ {-1} $或更大的系统,且其范式的相对误差为$ u $,前提是要用足够的相对误差解决更新方程少于$ 1 $。给出了新的舍入误差分析,并分析了其含义。在分析的基础上,我们开发了基于GMRES的迭代优化方法(GMRES-IR),该方法利用计算出的LU因子作为前置条件。 GMRES-IR利用了这样一个事实,即使$ A $病情严重,LU因子也包含足够的信息,因此预处理可以大大减少$ A $的病情数。我们的舍入误差分析和数值实验表明,在标准细化失败的情况下GMRES-IR可以成功,并且它可以为条件序号为$ u ^ {-1} $或更大的系统提供准确的解决方案。的确,在我们使用此类矩阵进行的实验中(无论是随机的还是佛罗里达大学稀疏矩阵集合的矩阵),GMRES-IR在每种情况下在最多$ 3 $的步长内都产生阶次u阶的相对误差。
展开▼